//
//  XMFourDimGrid.m
//  TestView
//
//  Created by lk@wxm on 2024/12/7.
//

#import "XMFourDimGrid.h"
@interface XMNode:NSObject
@property(nonatomic,strong)id value;
@property(nonatomic,strong)XMNode* left;
@property(nonatomic,strong)XMNode* right;
@property(nonatomic,strong)XMNode* up;
@property(nonatomic,strong)XMNode* down;
- (instancetype)initWithValue:(id)value;
@end

@interface XMFourDimGrid ()
@property(nonatomic,strong)XMNode* root;
//-(void)creatMapWithSize:(NSInteger)size;
@end

@implementation XMNode
- (instancetype)initWithValue:(id)value{
    if (self = [super init]) {
        self.value = value;
    }
    return self;
}

@end

@implementation XMFourDimGrid
- (void)creatMapWithSize:(NSInteger)size{
    if (size<=0) {
        size = 2;
    }
    NSMutableArray <XMNode*>*prerows = [NSMutableArray arrayWithCapacity:size];
    for (int i=0; i<size; i++) {
        [prerows addObject:[[XMNode alloc]initWithValue:@""]];
    }
    XMNode *preNode = nil;
    for (int i=0; i<size; i++) {
        preNode = nil;
        for (int j=0; j<size; j++) {
            XMNode *newNode = [[XMNode alloc]initWithValue:nil];
            if (self.root==nil) {
                self.root = newNode;
            }
            if (preNode) {
                newNode.left = preNode;
                preNode.right = newNode;
            }
            preNode = newNode;
            if (![prerows[j].value isEqualToString:@""]) {
                XMNode *preRowNode = prerows[j];
                newNode.up = preRowNode;
                preRowNode.down = newNode;
            }
//            if (![prerows[j] isEqual:[NSNull null]]) {
//                XMNode *preRowNode = prerows[j];
//                newNode.up = preRowNode;
//                preRowNode.down = newNode;
//            }
            prerows[j]=newNode;
        }
    }
    [self findCenter:size];
    [self printNodeMap];
}
-(void)printNodeMap{
    XMNode *node = self.root;
    while (node) {
        XMNode *row = node;
        while (row) {
            NSString *value = row.value ?: @".";
            printf("%s ",[value UTF8String]);
            row = row.right;
        }
        printf("\n");
        node = node.down;
    }
}
- (void)findCenter:(NSInteger)size{
    XMNode *center = self.root;
    for (int i=0; i<size/2; i++) {
        center = center.right;
    }
    for (int i=0; i<size/2; i++) {
        center = center.down;
    }
    center.value = @"B";
//    center.left.value = @"W";
//    center.left.up.value = @"B";
//    center.up.value = @"W";
}

//- (NSInteger)climbStairs:(NSInteger)n{
//    // 边界条件
//       if (n == 1) {
//           return 1;
//       }
//       
//       // 用于存储结果的动态规划数组
//       NSMutableArray *dp = [NSMutableArray arrayWithCapacity:n + 1];
//       dp[0] = @(1); // dp[0] = 1
//       dp[1] = @(1); // dp[1] = 1
//       
//       // 动态规划：计算 dp[2] 到 dp[n]
//       for (NSInteger i = 2; i <= n; i++) {
//           dp[i] = @([dp[i - 1] integerValue] + [dp[i - 2] integerValue]);
//       }
//       
//       // 返回到达第 n 阶的方法数
//       return [dp[n] integerValue];
//}

@end

@interface TreeNode : NSObject
@property (nonatomic, assign) NSInteger value;
@property (nonatomic, strong) TreeNode *left;
@property (nonatomic, strong) TreeNode *right;

- (instancetype)initWithValue:(NSInteger)value;
@end

@implementation TreeNode

- (instancetype)initWithValue:(NSInteger)value {
    self = [super init];
    if (self) {
        _value = value;
        _left = nil;
        _right = nil;
    }
    return self;
}

@end
@interface TreeNodeTest : NSObject

@end
@implementation TreeNodeTest
+(BOOL)isCompleteBinaryTree:(TreeNode *)root{
    if (root == nil) {
        return YES;
    }
    
    NSMutableArray<TreeNode *> *queue = [NSMutableArray array];
    [queue addObject:root];
    
    BOOL foundNullNode = NO;  // 标记是否遇到空节点
    
    while (queue.count > 0) {
        TreeNode *node = queue.firstObject;
        [queue removeObjectAtIndex:0];
        
        // 如果已经遇到空节点，后续的节点必须是空节点
        if (node == nil) {
            foundNullNode = YES;
        } else {
            // 如果遇到非空节点，且之前已经遇到过空节点，则不是完全二叉树
            if (foundNullNode) {
                return NO;
            }
            [queue addObject:node.left];
            [queue addObject:node.right];
        }
    }
    
    return YES;
}
@end
